<!DOCTYPE html>
<html lang="en">
<head>
    <meta charset="UTF-8">
    <meta http-equiv="X-UA-Compatible" content="IE=edge">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>Document</title>
    <script>
        function Dijkstra(matrix, start) {
            const rows = matrix.length,//rows和cols一样，其实就是顶点个数
            cols = matrix[0].length;
        
            if(rows !== cols || start >= rows) return new Error("邻接矩阵错误或者源点错误");
        
            //初始化distance
            let distance = new Array(rows).fill(Infinity);
            // 初始化访问节点
            let visited = new Array(rows).fill(false);
            distance[start] = 0;
        
            for(let i = 0; i < rows; i++) {
                // 更新节点访问
                visited[start] = true
                // 达到不了的顶点不能作为中转跳点
                if(distance[start] < Infinity) {
                    for(let j = 0; j < cols; j++) {
                        //通过比较distance[start] + matrix[start][j]和distance[j]的大小来决定是否更新distance[j]。
                        if(matrix[start][j] + distance[start] < distance[j]) {
                            distance[j] = matrix[start][j] + distance[start];
                        }
                    }
                }
                
                // 找到当前最短路径顶点作为中转跳点
                let minIndex = -1;
                let min = Infinity;
                for(let k = 0; k < rows; k++) {
                    if (!visited[k] && distance[k] < min) {
                        min = distance[k];
                        minIndex = k;
                    }
                }
                start = minIndex
            }
            return distance;
        }
    //     function Node(val, pre) {
    //         this.val = val // 当前距离
    //         this.pre = pre || null // 中转（前置）节点
    //     }
 
    //     function Dijkstra(matrix, start = 0) {
    //         const rows = matrix.length,//rows和cols一样，其实就是顶点个数
    //         cols = matrix[0].length;
 
    //         if(rows !== cols || start >= rows) return new Error("邻接矩阵错误或者源点错误");
 
    // //初始化distance
    //         let distance = new Array(rows)
    //         for (let i =0;i<rows;++i) {
    //             distance[i] = new Node(Infinity)
    //         }
    // // 初始化访问节点
    //         let visited = new Array(rows).fill(false);
    //         distance[start] = new Node(0);
    //         console.log(distance);
    // // 存在节点未访问则循环
    //         while(visited.some(item => !item)) {
    //             // 更新节点访问
    //             visited[start] = true
    //             // 达到不了的顶点不能作为中转跳点
    //             if(distance[start].val < Infinity) {
    //                 for(let j = 0; j < cols; j++) {
    //                     //通过比较distance[start] + matrix[start][j]和distance[j]的大小来决定是否更新distance[j]。
    //                     if(matrix[start][j] + distance[start].val < distance[j].val) {
    //                         distance[j].val = matrix[start][j] + distance[start].val;
    //                         distance[j].pre = start
    //                     }
    //                 }
    //             }
                
    //             // 找到当前最短路径顶点作为中转跳点
    //             let minIndex = -1;
    //             let min = Infinity;
    //             for(let k = 0; k < rows; k++) {
    //                 if (!visited[k] && distance[k].val < min) {
    //                     min = distance[k].val;
    //                     minIndex = k;
    //                 }
    //             }
    //             start = minIndex
    //         }
    //         return distance;
    //     }
        function Matrix(graph, a, x, y){
            const MAX_INTEGER = Infinity;//没有边或者有向图中无法到达
            const MIN_INTEGER = 0;
            var matrix = [];
            for(var weight=0; weight<a; weight++){
                matrix[weight] = [];
                for(var i=0; i<graph.length; i++){
                    for(var j=0; j<graph[0].length; j++){
                        matrix[weight][i*graph[0].length+j] = Infinity;
                        if(weight == i*graph[0].length+j){matrix[weight][i*graph[0].length+j] = MIN_INTEGER;}
                    }
                }
                if(x == 1 && (weight%graph[0].length+1)<graph[0].length){
                    matrix[weight][weight+1] = 
                        Math.abs(graph[parseInt(weight/graph[0].length)][weight%graph[0].length+1]
                                -graph[parseInt(weight/graph[0].length)][weight%graph[0].length]);
                }else if(x == -1 && (weight%graph[0].length-1)>=0){
                    matrix[weight][weight-1] = 
                        Math.abs(graph[parseInt(weight/graph[0].length)][weight%graph[0].length-1] 
                                -graph[parseInt(weight/graph[0].length)][weight%graph[0].length]);

                }
                if(y == 1 && (parseInt(weight/graph[0].length)-1)>=0){
                    matrix[weight][weight-graph[0].length] = 
                        Math.abs(graph[parseInt(weight/graph[0].length)][weight%graph[0].length] 
                                 -graph[parseInt(weight/graph[0].length)-1][weight%graph[0].length]);
                }else if(y == -1 && (parseInt(weight/graph[0].length)+1)<graph.length){
                    matrix[weight][weight+graph[0].length] = 
                        Math.abs(graph[parseInt(weight/graph[0].length)][weight%graph[0].length] 
                                -graph[parseInt(weight/graph[0].length)+1][weight%graph[0].length]);
                }
            }
            return matrix;
        }
        var a = 5;
        var map = [
            [1, 3, 8, 2, 2],
            [3, 2, 0, 8, 2],
            [3, 2, 6, 8, 1],
            [1, 0, 6, 3, 9],
            [4, 0, 8, 2, 8]
        ];
        //1 获取start，end
        var startX = parseInt(prompt("Start point X"));
        var startY = parseInt(prompt("Start point Y"));
        var endX = parseInt(prompt("End point X"));
        var endY = parseInt(prompt("End point Y"));
        console.log("用户输入起始位置：" + startX, startY);

        var start = map[startX][startY];
        var end = map[endX][endY];

        var x, y = 0;
        //方向
        if(endX - startX <= 0){
            x = 1; //右
        }else{
            x = -1;
        }
        if(endY - startY >= 0){
            y = 1; //上
        }else{
            y = -1;
        }

        //生成固定范围
        var graph = [];
        var xn = Math.min(startX, endX);
        var yn = Math.min(startY, endY);
        var xx = Math.max(startX, endX);
        var yx = Math.max(startY, endY);
        var i = 0;
        while(i <= xx-xn){
            var j =0;
            graph[i] = [];
            while(j <= yx-yn){
                graph[i][j] = map[xn+i][yn+j];
                j++;
            }
            i++;
        }

        //生成矩阵
        var matrix = Matrix(graph, graph.length*graph[0].length, x, y);
        //position
        var spx, spy, epx, epy;
        if(startX >= endX){
            spx = graph.length-1;
            epx = 0;
        }else{
            spx = 0;
            epx = graph.length-1;
        }
        if(startY <= endY){
            spy = 0;
            epy = graph[0].length-1;
        }else{
            spy = graph[0].length-1;
            epy = 0;
        }
        
        console.log(spx*graph[0].length+spy)
        //Dijkstra
        var arr = Dijkstra(matrix, spx*graph[0].length+spy);
        console.log(arr);
        console.log("最短路程为：", arr[epx*graph[0].length+epy]);

    </script>
</head>
<body>
    
</body>
</html>